package LC;

import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.com/problems/path-sum-ii/description/
 * Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
 * For example:
 * Given the below binary tree and sum = 22,
 */
public class LC_113_PathSumII_BinaryTree_Recur {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(1);
        List<List<Integer>> lists = Solution.pathSum(root, 4);
        System.out.println(lists);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        static private List<List<Integer>> result;
        static private List<Integer> l;
        static private int sum_1;
        static private int curSum = 0;

        static List<List<Integer>> pathSum(TreeNode root, int sum) {
            result = new LinkedList<>();
            if (root != null) {
                sum_1 = sum;
                l = new LinkedList<>();
                pathSum(root);
            }
            return result;
        }

        private static void pathSum(TreeNode root) {
            if (root != null) {
                l.add(root.val);
                curSum += root.val;
                if (root.left == null && root.right == null && curSum == sum_1) {
                    List<Integer> list = new LinkedList<>();
                    list.addAll(l);
                    result.add(list);
                }
                if (root.left != null) pathSum(root.left);
                if (root.right != null) pathSum(root.right);
                curSum -= root.val;
                l.remove(l.size() - 1);
            }
        }

    }
}